/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-05-15
 * Time: 19:34
 */
public class test_2 {
    public static int minFallingPathSum(int[][] matrix) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n=matrix.length;
        int[][] dp=new int[n+1][n+2];
        for (int i = 0; i <= n; i++) {
            dp[i][0]=dp[i][n+1]=Integer.MAX_VALUE;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j]=matrix[i-1][j-1]+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i-1][j+1]));
            }
        }
        int ret = Integer.MAX_VALUE;
        for(int j = 1; j <= n; j++)
             ret = Math.min(ret, dp[n][j]);
         return ret;
    }
}
